package dataStructure.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 浦希成gitpu
 * 2018/9/23 17:27
 */
public class NodeQuery {
    public static void preOrder(TreeNode root) { // 前序遍历(递归的方式)
        if (root != null) {
            System.out.print(root.data + "-");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public static void inOrder(TreeNode root) { // 中根遍历

        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + "-");
            inOrder(root.right);
        }
    }

    public static void postOrder(TreeNode root) { // 后根遍历

        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + "-");
        }
    }

    public  static void preOrderNonRecursive(TreeNode root) { //前序遍历(非递归的方式)
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            //所有左子树入栈
            while (root != null) {
                System.out.print(root.data + "--");
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop();
            root = root.right;
        }
    }

    public static void inOrderNonRecursive(TreeNode root) {//中序遍历(非递归的方式)
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop();
            System.out.print(root.data + "--");
            root = root.right;
        }
    }

    public static void postOrderNonRecursive(TreeNode root) {//后序遍历(非递归的方式)
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                if (stack.isEmpty()) {
                    return;
                }
                if (null == stack.lastElement().right) {
                    root = stack.pop();
                    System.out.print(root.data + "--");
                    while (root == stack.lastElement().right) {
                        System.out.print(stack.lastElement().data+"--");
                        root = stack.pop();
                        if (stack.isEmpty()) {
                            break;
                        }
                    }
                }
                if (!stack.isEmpty()) {
                    root = stack.lastElement().right;
                } else {
                    root = null;
                }
            }
        }
    }

    public static void levelOrder(TreeNode root) { //层序遍历
        TreeNode temp;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.print(root.data + "--");
            if (null != temp.left) {
                queue.offer(temp.left);
            }
            if (null != temp.right) {
                queue.offer(temp.right);
            }
        }
    }

    public static void main(String[] args) {
        //创建二叉树
        TreeNode root = Util.createTree();

        System.out.println("先序遍历：");
        preOrder(root);
        System.out.println();

        System.out.println("中序遍历：");
        inOrder(root);
        System.out.println();

        System.out.println("后序遍历：");
        postOrder(root);
        System.out.println();

        System.out.println("先序遍历(非递归的方式)：");
        preOrderNonRecursive(root);
        System.out.println();

        System.out.println("中序遍历(非递归的方式)：）");
        inOrderNonRecursive(root);
        System.out.println();

        System.out.println("后序遍历(非递归的方式)：）");
        postOrderNonRecursive(root);
        System.out.println();

        System.out.println("层序遍历：");
        levelOrder(root);
    }
}
